package btree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 30
 * Time:10:12
 */

import java.util.Arrays;

/***
 * 暂时只考虑：
 * （1） 定义为key模型而不是key-value模型
 * （2）key类型定义为long类型
 */
public class BTreeNode {
    /***
     * 规定：一个B-树节点中，最多只能保存的key的数量的上限（要求size(key) < KEY_LIMIT）
     */
    public static final int KEY_LIMIT = 4;

    /***
     *保存节点中的所有key——使用数组（线性结构）进行维护，需要维护key与 key之间的有序性
     * 多申请一个空间，方便进行节点分裂代码的编写（用于保存即将分裂状态下的所有key）
     */
    public Long[] keyList = new Long[KEY_LIMIT + 1];

    /***
     * 记录目前拥有的key的数量
     */
    public int size = 0;

    /***
     * 维护节点中所有的child
     */
    public BTreeNode[] childList = new BTreeNode[KEY_LIMIT + 2];

    /***
     * child的个数一定是child +  1，此处不进行维护；
     */

    /***
     * 保存该节点的父节点，为null代表该节点是根节点
     */
    public BTreeNode parent = null;

    /***
     * 实现：
     * 给定节点值key,查找其位于当前节点的哪棵子树中
     * @param key  关键字
     * @return
     * this——代表key位于当前节点中
     * 其它：位于孩子节点中，其中孩子可能是null
     */

    public BTreeNode findKey(long key){
        //末尾的考虑
        if(key > keyList[size - 1]){
            //child比key多一个
            //keyList的最后一个元素位于【size- 1】
            //childList的最后一个元素位于【size】
            return childList[size];
        }
        //其它情况：进行遍历
        for (int i = 0; i < size; i++) {
            if(key == keyList[i]){
                //即key就在当前节点中；
                return this;
            }else if(key < keyList[i]){
                //由于我们是从左到右进行遍历的
                //所以keyList[i]中的元素就是 “第一个”大于key的关键字元素
                return  childList[i];
            }else {
                //key >keyList[i]的情况下，继续遍历查找
                //第一个大于key的元素
            }
        }
        //代码不会走到此处，为了不让编译器报错；return返回一个值；
        return null;
    }

    /***
     * 将key和child 插入到非叶子节点中
     * @param key
     * @param child
     * @return
     */
    public InsertResult insertKeyWithChild(long key, BTreeNode child) {
        return null;
    }

    /***
     * 用来作为插入的返回值类型的类
     */
    public static class InsertResult{
        public long key;//分裂出来的key
        public BTreeNode node;//分裂出来的新节点

    }

    /***
     * 将指定的关键字key，插入到叶子节点中
     * @param key
     * @return
     * 若返回值为null,代表插入之后不需要进行分裂；
     * 若返回值为 ！null ,代表发生了分裂；
     */
    public InsertResult insertKey(long key){
        //1.考虑如何将key按序插入到keyList中
        insertintoKeyList(key);
        size ++;
        //2.判断是否需要进行分裂

        //3.如果有必要，进行节点分裂；
        if(shouldSplit()){
            return splitLeaf();
        }
        return null;
    }

    /***
     * 当前节点进行分裂
     * @return
     */
    private InsertResult splitLeaf() {

        //记录size,中途会进行修改
        int size = this.size;

        InsertResult result = new InsertResult();
        BTreeNode node = new BTreeNode();

        //1.找到keyList的中间位置
        int index = size /2;
        //2.保存需要分裂出来的key
        result.key = keyList[index];

        /***
         * 3.处理key的分裂
         * 哪些key应该留在当前节点中——[0，index)——一共有index个
         * 哪些key是分裂出来的key——应该存放在[index]位置
         * 哪些key应该在新节点中—— （index,size) ——一共拥有size - index - 1;
         */
        //先把（index,size)位置的key移动到新节点中
        System.arraycopy(keyList,index + 1,node.keyList,0,size - index -1);
        node.size = size - index - 1;
        // 把{index,size) 所有的key重置为默认值0，重置size
        Arrays.fill(keyList,index,size,Long.valueOf(0));
        this.size = index;

        /***
         * 4.对叶子节点进行分裂；
         * 叶子节点没有孩子，即childList[...]  = null,不需要进行分裂
         */

        /***
         * 5.处理分裂parent的问题
         * （1）this.parent 不变；
         * （2）node.parent 和 this是同一个父亲
         */
        node.parent = this.parent;
        result.node = node;
        return result;
    }

    /***
     * 判断是否需要进行分裂
     * @return
     */
    public boolean shouldSplit(){
        return size > KEY_LIMIT;
    }

    private void insertintoKeyList(long key) {
        //keyList中有效的下标范围是[0,size)
        //从后向前遍历[size - 1,0]
        int i;
        for (i = size - 1;i >= 0;i--){
            if(keyList[i] < key){
                //第一次碰到了keyList[i] < key
                break;
            }
            //没有keyList[i] == key
            //继续遍历查找，同时将数据向后移动一个
            keyList[i + 1] = keyList[i];
        }

        //(1）越界情况 i == -1;
        //(2)keyList[i] < key;
        //不管怎样，将key放在[i + 1]位置
        keyList[i + 1] = key;
    }

    public static void testFindKey() {
        BTreeNode node = new BTreeNode();
        node.keyList[0] = Long.valueOf(10);
        node.keyList[1] = Long.valueOf(20);
        node.keyList[2] = Long.valueOf(30);
        node.keyList[3] = Long.valueOf(40);

        node.size = 4;

        BTreeNode 甲 = new BTreeNode();
        BTreeNode 乙 = new BTreeNode();
        BTreeNode 丙 = new BTreeNode();
        BTreeNode 丁 = new BTreeNode();
        BTreeNode 戊 = new BTreeNode();
        node.childList[0] = 甲;
        node.childList[1] = 乙;
        node.childList[2] = 丙;
        node.childList[3] = 丁;
        node.childList[4] = 戊;

        //进行测试
        /***
         * 测试用例：执行动作以及期望结果
         *  < 10 —— 甲
         *  == 10 —— node
         *  == 20 —— node
         *  （10,20）—— 乙
         *  （20,30）—— 丙
         *  （30,40) ——丁
         *   > 40 —— 戊
         *   == 40 —— node
         */

        /***
         * 引用1 == 引用2 ——判断两个引用是否指向同一个对象
         */
        System.out.println(node.findKey(3) == 甲);
        System.out.println(node.findKey(10) == node);
        System.out.println(node.findKey(20) == node);
        System.out.println(node.findKey(13) == 乙);
        System.out.println(node.findKey(29) == 丙);
        System.out.println(node.findKey(31) == 丁);
        System.out.println(node.findKey(300) == 戊);
        System.out.println(node.findKey(40) == node);
    }

    /***
     * 插入节点key代码测试
     */
    public static void testInsertKey(){
        BTreeNode parent = new BTreeNode();

        BTreeNode node = new BTreeNode();
        node.parent = parent;

        // 第一个测试用例
        // 理论上这个不应该测，因为 B-树的插入过程中从不会有往一个空的(不是 null)结点中插入的
        // B-树的结点都是分裂出来的，不是手动 new 出来的
        // B-树一定包含从原来的结点中分出来的 key
        InsertResult r = node.insertKey(15);
        System.out.println(r == null);
        System.out.println(node.size == 1);
        System.out.println(node.keyList[0] == 15);
        System.out.println(node.parent == parent);

        // 测试用例 2
        r = node.insertKey(7);
        System.out.println(r == null);
        System.out.println(node.size == 2);
        System.out.println(node.keyList[0] == 7);
        System.out.println(node.keyList[1] == 15);
        System.out.println(node.parent == parent);

        // 测试用例 3
        r = node.insertKey(19);
        System.out.println(r == null);
        System.out.println(node.size == 3);
        System.out.println(node.keyList[0] == 7);
        System.out.println(node.keyList[1] == 15);
        System.out.println(node.keyList[2] == 19);
        System.out.println(node.parent == parent);

        // 测试用例 4
        r = node.insertKey(10);
        System.out.println(r == null);
        System.out.println(node.size == 4);
        System.out.println(node.keyList[0] == 7);
        System.out.println(node.keyList[1] == 10);
        System.out.println(node.keyList[2] == 15);
        System.out.println(node.keyList[3] == 19);
        System.out.println(node.parent == parent);

        // 测试用例 5
        r = node.insertKey(17);
        System.out.println(r != null);
        System.out.println(node.size == 2);
        System.out.println(node.keyList[0] == 7);
        System.out.println(node.keyList[1] == 10);
        System.out.println(node.keyList[2] == 0);
        System.out.println(node.keyList[3] == 0);
        System.out.println(node.keyList[4] == 0);
        System.out.println(node.parent == parent);
        System.out.println(r.key == 15);
        System.out.println(r.node.size == 2);
        System.out.println(r.node.keyList[0] == 17);
        System.out.println(r.node.keyList[1] == 19);
        System.out.println(node.keyList[2] == 0);
        System.out.println(node.keyList[3] == 0);
        System.out.println(node.keyList[4] == 0);
        System.out.println(r.node.parent == parent);
    }


    public static void main(String[] args) {
        //testFindKey();
        testInsertKey();
    }

    /***
     * 节点key的插入
     * 此时，key一定不再该节点中
     * 结果：
     * （1）插入之后，不需要进行分裂
     * （2）插入之后，需要进行分裂
     * BTreeNode current  ——> 节点分裂 ——>long KeySplit  BtreeNode nodeSplit(由于节点分裂多出来的数据)
     * 所以，插入的返回值可以体现出：
     * （1）插入之后是否发生了分裂；
     * （2）如果发生了分裂，分裂出的key是什么？
     * （3）如果发生了分裂，分裂出的node节点是什么？
     * @param key
     * @return
     */
    public InsertResult insert(long key) {
        return null;
    }
}
